import java.util.Arrays;
import java.util.Random;

class Solution195QuickSelect {
    public int[] inventoryManagement(int[] stock, int cnt) {
         quick(stock , 0 , stock.length-1 , cnt) ;       
         return Arrays.copyOfRange(stock , 0 , cnt) ; // 通过快速选择后 , 最小的k个元素在[0,k]区间里了
    }
    private void quick(int[] nums , int l , int r , int cnt) {
        if(l >= r || cnt <= 0)return  ;
        Random rand = new Random() ;
        int key = nums[rand.nextInt(r-l+1)+l];
        int left = l-1 , right = r+1 ; 
        for(int i=l ; i < right ; ){
            if(nums[i] < key){
                swap(nums , ++left , i++) ;
            }else if(nums[i] > key){
                swap(nums , --right , i) ; 
            }else{
                i ++ ;
            }
        }
        int a = left-l+1 , b = right-left-1 , c = r-right+1 ;
        if(a >= cnt){   // 在a区间里找最下的k个元素
             quick(nums ,l , left , cnt) ; 
        }else if(a + b >= cnt){  // 因为b区间的元素都是一样 的, 同时k>a , a+b>=k , 所以a区间里就已经有a个最小的元素,
           return ;              //  加上 k-a个元素在b区间里,b区间里的数都相同, 所以直接返回 , 因为[0,b]区间,已经有最小的k个元素
        }else {         //k > a+b , 表示 [a+b]区间里已经有最小的a+b个元素 , 但还不够 , 还有 k-a-b个元素在c区间里
            quick(nums , right , r , cnt-a-b) ; 
        }
    }
    private void swap(int[] nums , int i , int j){
        int tmp = nums[i] ; 
        nums[i] = nums[j] ; 
        nums[j] = tmp ;
    } 
}